#ifndef KDTREE_H
#define KDTREE_H

#include "Plano.h"
#include <QVector>
#include "Triangulo.h"
#include "Objeto_3d.h"
#include "BoundingBox.h"

#define MINFILHOS 2
#define NDIM 3
#define EIXO(v) ((v)%(NDIM))
#define EIXO_X 0
#define EIXO_Y 1
#define EIXO_Z 2

typedef struct _NO
{
    Plano* corte;
    QVector<Triangulo*> *folha;
    BoundingBox bbe;
    BoundingBox bbd;
    _NO *esq;
    _NO *dir;
}NO;

class KDTree
{
public:
    NO* raiz;
    KDTree() {}
    int constroi(const QVector<Triangulo*>& array, BoundingBox bb);
    const Objeto_3D* intecepta(const Raio& r_vis, float* t) const;
private:
    NO* divide(QVector<Triangulo*>* vet, BoundingBox bb, int nivel);
    const Objeto_3D* busca(const Raio& r_vis, float* t,NO* no ,int nivel) const;
    const Objeto_3D* buscaLinear(const Raio& r_vis, float* ret, const QVector<Triangulo*>& vet) const;
    float mediana(const QVector<Triangulo*>& vet, int nivel);
    void separa(const QVector<Triangulo*>& vet, QVector<Triangulo*> *vesq,
                QVector<Triangulo*> *vdir, float val, int nivel);

};

#endif // KDTREE_H
